﻿// 版权所有：
// 文 件  名：HeapSort.cs
// 功能描述：
// 创建标识：Seven Song(m.sh.lin0328@163.com) 2014/5/01 14:49:57
// 修改描述：
//----------------------------------------------------------------*/
using System;
using System.Collections.Generic;

using System.Text;

namespace MSL.Utility.Sort
{
    /// <summary>
    /// 堆排序 原理：
    /// </summary>
    public class HeapSort : SortBase, ISort
    {
        /// <summary>
        /// 降序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Desc<T>(IList<T> list) where T : IComparable
        {
            SortCore(list,false);
        }
        /// <summary>
        /// 升序
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        public void Asc<T>(IList<T> list) where T : IComparable
        {
            SortCore(list, true);
        }

        #region 私有方法
        
        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        /// <param name="isAsc">是否升序</param>
        private void SortCore<T>(IList<T> list, bool isAsc) where T : IComparable
        {
            BuildMaxHeapify(list, isAsc);
            int j = list.Count;
            for (int i = 0; i < j; )
            {
                Swap(list, i, --j);
                if (j - 2 < 0)  //只剩下1个数 j代表余下要排列的数的个数
                    break;
                int k = 0;
                while (true)
                {
                    if (k > (j - 2) / 2) break;  //即：k > ((j-1)-1)/2 超出最后一个父节点的位置  
                    else
                    {
                        int temp = k;
                        k = ReSortMaxBranch(list, k, 2 * k + 1, 2 * k + 2, j - 1, isAsc);
                        if (temp == k) break;
                    }
                }
            }
        }
        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        /// <param name="isAsc">是否升序</param>
        private void BuildMaxHeapify<T>(IList<T> list, bool isAsc) where T : IComparable
        {
            for (int i = list.Count / 2 - 1; i >= 0; i--)  //(data.Count-1)-1)/2为数列最大父节点索引
            {
                int temp = i;
                temp = ReSortMaxBranch(list, i, 2 * i + 1, 2 * i + 2, list.Count - 1, isAsc);
                if (temp != i)
                {
                    int k = i;
                    while (k != temp && temp <= list.Count / 2 - 1)
                    {
                        k = temp;
                        temp = ReSortMaxBranch(list, temp, 2 * temp + 1, 2 * temp + 2, list.Count - 1, isAsc);
                    }
                }
            }
        }
        /// <summary>
        /// 
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list">集合</param>
        /// <param name="max">最大索引</param>
        /// <param name="low">低索引</param>
        /// <param name="height">高索引</param>
        /// <param name="last"></param>
        /// <param name="isAsc">是否升序</param>
        /// <returns></returns>
        private int ReSortMaxBranch<T>(IList<T> list, int max, int low, int height, int last, bool isAsc) where T : IComparable
        {
            int temp;
            if (height > last)  //父节点只有一个子节点
            {
                temp = low;
            }
            else
            {
                if (isAsc)
                {
                    temp = list[low].CompareTo(list[height]) > 0 ? low : height;
                }
                else
                {
                    temp = list[low].CompareTo(list[height]) > 0 ? height : low;
                }
            }
            if (isAsc && list[max].CompareTo(list[temp]) < 0)
            {
                Swap(list, max, temp);
            }
            else if (!isAsc && list[max].CompareTo(list[temp]) > 0)
            {
                Swap(list, max, temp);
            }
            else
            {
                temp = max;
            }
            return temp;
        }
        #endregion
    }
}
